try:
    import graphviz
except ImportError:
    graphviz = None
    
class GraphNode:
    """
    GraphNode represents a node in a graph.

    Attributes:
        data: Data stored in the node.
        neighbors: List of neighboring nodes.
    """

    def __init__(self, data=None):
        """
        Initialize a GraphNode with data and an empty list of neighbors.

        Args:
            data: Initial data for this node. Defaults to None.
        """
        self.data = data
        self.neighbors = []

    def add_neighbor(self, node):
        """
        Add a neighboring node to the current node.

        Args:
            node: Neighboring node to be added.
        """
        self.neighbors.append(node)

    def remove_neighbor(self, node):
        """
        Remove a neighboring node from the current node.

        Args:
            node: Neighboring node to be removed.
        """
        self.neighbors.remove(node)

    def is_neighbor(self, node):
        """
        Check if the given node is a neighbor of the current node.

        Args:
            node: Node to check.

        Returns:
            True if the node is a neighbor, False otherwise.
        """
        return node in self.neighbors

    def __str__(self):
        """
        Return a string representation of the node.

        Returns:
            A string representation of the node.
        """
        return str(self.data)


class DirectedGraph:
    """
    DirectedGraph represents a directed graph.

    Attributes:
        nodes: List of nodes in the graph.
    """

    def __init__(self):
        """
        Initialize an empty graph with no nodes.
        """
        self.nodes = []

    def add_node(self, data):
        """
        Add a node to the graph.

        Args:
            data: Data for the node.
        """
        node = GraphNode(data)
        self.nodes.append(node)

    def remove_node(self, node):
        """
        Remove a node from the graph.

        Args:
            node: Node to be removed.
        """
        if node in self.nodes:
            self.nodes.remove(node)
            for n in self.nodes:
                if n.is_neighbor(node):
                    n.remove_neighbor(node)

    def add_edge(self, from_node, to_node):
        """
        Add a directed edge from a source node to a target node.

        Args:
            from_node: Source node.
            to_node: Target node.
        """
        if from_node in self.nodes and to_node in self.nodes:
            from_node.add_neighbor(to_node)

    def remove_edge(self, from_node, to_node):
        """
        Remove a directed edge from a source node to a target node.

        Args:
            from_node: Source node.
            to_node: Target node.
        """
        if from_node in self.nodes and to_node in self.nodes:
            from_node.remove_neighbor(to_node)

    def get_nodes(self):
        """
        Get a list of nodes in the graph.

        Returns:
            List of nodes.
        """
        return self.nodes

    def breadth_first_traversal(self):
        """
        Perform breadth-first traversal of the graph and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        queue = []
        for node in self.nodes:
            if node not in visited:
                queue.append(node)
                visited.add(node)
                while queue:
                    current_node = queue.pop(0)
                    print(current_node.data)
                    for neighbor in current_node.neighbors:
                        if neighbor not in visited:
                            queue.append(neighbor)
                            visited.add(neighbor)

    def depth_first_traversal_recursive(self):
        """
        Perform depth-first traversal of the graph using recursion and print the node values.
        """
        if not self.nodes:
            return
        visited = set()

        def dfs(node):
            visited.add(node)
            print(node.data)
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    dfs(neighbor)

        for node in self.nodes:
            if node not in visited:
                dfs(node)

    def depth_first_traversal_iterative(self):
        """
        Perform depth-first traversal of the graph using iteration and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        stack = []
        for node in self.nodes:
            if node not in visited:
                stack.append(node)
                while stack:
                    current_node = stack.pop()
                    if current_node not in visited:
                        print(current_node.data)
                        visited.add(current_node)
                        for neighbor in current_node.neighbors:
                            if neighbor not in visited:
                                stack.append(neighbor)

    def depth_first_traversal_preorder(self):
        """
        Perform depth-first traversal of the graph in preorder and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        stack = []

        for node in self.nodes:
            if node not in visited:
                stack.append(node)
                while stack:
                    current_node = stack.pop()
                    if current_node not in visited:
                        visited.add(current_node)
                        print(current_node.data)
                        for neighbor in reversed(current_node.neighbors):
                            if neighbor not in visited:
                                stack.append(neighbor)

    def depth_first_traversal_inorder(self):
        """
        Perform depth-first traversal of the graph in inorder and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        stack = []
        for node in self.nodes:
            if node not in visited:
                stack.append(node)
                while stack:
                    current_node = stack[-1]
                    if current_node in visited:
                        stack.pop()
                    else:
                        visited.add(current_node)
                        for neighbor in current_node.neighbors:
                            if neighbor not in visited:
                                stack.append(neighbor)
                                break
                        else:
                            print(current_node.data)

    def depth_first_traversal_postorder(self):
        """
        Perform depth-first traversal of the graph in postorder and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        stack = []
        for node in self.nodes:
            if node not in visited:
                stack.append(node)
                while stack:
                    current_node = stack[-1]
                    if current_node in visited:
                        stack.pop()
                        print(current_node.data)
                    else:
                        visited.add(current_node)
                        for neighbor in current_node.neighbors:
                            if neighbor not in visited:
                                stack.append(neighbor)
                                break

    def size(self):
        """
        Calculate the size (number of nodes) of the graph.

        Returns:
            Size of the graph.
        """
        return len(self.nodes)

    def height(self):
        """
        Calculate the height of the graph.

        Returns:
            Height of the graph.
        """
        if not self.nodes:
            return 0
        heights = []

        def calculate_height(node):
            if not node.neighbors:
                return 1
            else:
                child_heights = [calculate_height(neighbor) for neighbor in node.neighbors if neighbor not in heights]
                return max(child_heights) + 1

        for node in self.nodes:
            heights.append(calculate_height(node))
        return max(heights)

    def depth(self, node):
        """
        Calculate the depth of a node in the graph.

        Args:
            node: Node for which to calculate the depth.

        Returns:
            Depth of the node.
        """
        return self._depth_helper(node, 0)

    def _depth_helper(self, node, depth):
        """
        Helper method for calculating the depth of a node in the graph.

        Args:
            node: Current node being visited.
            depth: Current depth in the graph.

        Returns:
            Depth of the node.
        """
        if not node.neighbors:
            return depth
        depths = [self._depth_helper(neighbor, depth + 1) for neighbor in node.neighbors]
        return max(depths)

    def is_internal_node(self, node):
        """
        Check if a given node is an internal node.

        Args:
            node: Node to check.

        Returns:
            True if the node is internal, False otherwise.
        """
        return bool(node.neighbors)

    def __str__(self):
        """
        Return a string representation of the graph.

        Returns:
            A string representation of the graph.
        """
        if not graphviz:
            return self._graphviz_str()
        else:
            return self._ascii_str()

    def _graphviz_str(self):
        dot = graphviz.Digraph(graph_attr={'rankdir': 'LR'})

        for node in self.nodes:
            dot.node(str(node))

        for node in self.nodes:
            for neighbor in node.neighbors:
                dot.edge(str(node), str(neighbor))
        dot.render(filename=f'{self.size()}', format='png', view=True)

        return dot.source

    def _ascii_str(self):
        lines = []
        for node in self.nodes:
            neighbors = [str(neighbor) for neighbor in node.neighbors]
            line = f"{str(node)} : {' '.join(neighbors)}" if neighbors else str(node)
            lines.append(line)
        return "\n".join(lines)


if __name__ == "__main__":
    # Create a new directed graph
    my_graph = DirectedGraph()

    # Add nodes to the graph
    my_graph.add_node("A")
    my_graph.add_node("B")
    my_graph.add_node("C")
    my_graph.add_node("D")
    my_graph.add_node("E")

    # Add edges between nodes
    my_graph.add_edge(my_graph.get_nodes()[0], my_graph.get_nodes()[1])
    my_graph.add_edge(my_graph.get_nodes()[0], my_graph.get_nodes()[2])
    my_graph.add_edge(my_graph.get_nodes()[1], my_graph.get_nodes()[3])
    my_graph.add_edge(my_graph.get_nodes()[2], my_graph.get_nodes()[3])
    my_graph.add_edge(my_graph.get_nodes()[3], my_graph.get_nodes()[4])

    # Print the graph structure
    print("Graph structure:")
    print(my_graph)
    # Output:
    # Graph structure:
    # A : B C
    # B : D
    # C : D
    # D : E
    # E :

    # Perform breadth-first traversal
    print("Breadth-first traversal:")
    my_graph.breadth_first_traversal()
    # Output:
    # A
    # B
    # C
    # D
    # E

    # Perform recursive depth-first traversal
    print("Recursive Depth-first traversal:")
    my_graph.depth_first_traversal_recursive()
    # Output:
    # A
    # B
    # D
    # E
    # C

    # Perform iterative depth-first traversal
    print("Iterative Depth-first traversal:")
    my_graph.depth_first_traversal_iterative()
    # Output:
    # A
    # B
    # D
    # E
    # C

    # Perform depth-first traversal in preorder
    print("Preorder Depth-first traversal:")
    my_graph.depth_first_traversal_preorder()
    # Output:
    # A
    # B
    # D
    # E
    # C

    # Perform depth-first traversal in inorder
    print("Inorder Depth-first traversal:")
    my_graph.depth_first_traversal_inorder()
    # Output:
    # B
    # A
    # D
    # E
    # C

    # Perform depth-first traversal in postorder
    print("Postorder Depth-first traversal:")
    my_graph.depth_first_traversal_postorder()
    # Output:
    # B
    # D
    # E
    # C
    # A

    # Remove a node from the graph
    my_graph.remove_node(my_graph.get_nodes()[2])

    # Print the graph structure after removing a node
    print("Graph structure after removing a node:")
    print(my_graph)
    # Output:
    # Graph structure after removing a node:
    # A : B
    # B : D
    # D : E
    # E :
